package com.xigua._递归;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: ${todo}
 * @date 2022/4/714:23
 */
public class _22_括号生成 {

    List<String> ans = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        dfs("",n,n);
        return ans;
    }

    private void dfs(String s, int left, int right) {
        if (left == 0 && right == 0){
            ans.add(s);
            return;
        }else if (left == 0){
            dfs(s+")",left,right-1);
        }else if (left == right){
            dfs(s+"(",left-1,right);
        }else {
            dfs(s+"(",left-1,right);
            dfs(s+")",left,right-1);
        }
    }

}
